Linear cost Sorting

- 계수 정렬(Counting Sort)

- 기수 정렬(Radix Sort)

- 버킷 정렬(Bucket Sort)
비교정렬(Compare Sorting)은 최악의 경우 \Omega(nlgn) 만큼 비교를 해주어야 한다.
병합정렬, 힙정렬은 점근적으로 최적의 정렬 방법이다.
Counting Sort
#include <iostream>
using namespace std;
void CountingSort(int* A, int* B, const int k, int size){
int* C=new int[k+1];
for(int j=0; j<size; ++j){
C[A[j]]++;
}
for(int i=1; i<k+1; ++i){
C[i]+=C[i-1];
}
for(int j=size-1; j>=0; --j){
B[C[A[j]]-1]=A[j];
C[A[j]]--;
}
delete[] C;
}
int main(void){
int A[]={2, 5, 3, 0, 2, 3, 0, 3, 7};
const int size=sizeof(A)/sizeof(int);
int B[size]={0, };
int k=0;
for(int i=0; i<size; ++i){
if(A[i]>k) k=A[i];
}
CountingSort(A, B, k, size);
for(int i=0; i<size-1; ++i){
cout<<B[i]<<", ";
}
cout<<B[size-1]<<endl;
}
Radix Sort
#include <iostream>
#include <cmath>
using namespace std;
int number(int num, int digit){
assert(digit>0);
int upper=pow(10, digit), down=pow(10, digit-1);
return (num%upper)/down;
}
void CountingSort(int* A, const int k, int size, int digit){
int* C=new int[k+1];
int* B=new int[size];
for(int j=0; j<size; ++j){
C[number(A[j], digit)]++;
}
for(int i=1; i<k+1; ++i){
C[i]+=C[i-1];
}
for(int j=size-1; j>=0; --j){
B[C[number(A[j], digit)]-1]=A[j];
C[number(A[j], digit)]--;
}
for(int i=0; i<size; ++i){
A[i]=B[i];
}
delete[] B;
delete[] C;
}
void RadixSort(int*A, int d, int size){
int* B=new int[size];
for(int i=1; i<=d; ++i){
CountingSort(A, 9, size, i);
}
delete[] B;
}
int main(void){
int arr[]={329, 457, 657, 839, 436, 720, 355};
int num_size=3;
int size=sizeof(arr)/sizeof(int);
RadixSort(arr, num_size, size);
for(int i=0; i<size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[size-1]<<endl;
return 0;
}
Bucket Sort
입력이 균등 분포[0, 1)의 범위에서 균등하게 분포함을 가정한다.
(일반적으로 연결리스트로 구현)

편의를 위해 STL vector & STL list를 이용해 구현
#include <iostream>
#include <vector>
#include <list>
using namespace std;
void BucketSort(float *arr, int size){
list<float>* B=new list<float>[size];
for(int i=0; i<size; ++i){
int ind=static_cast<int>(size*arr[i]);
B[ind].push_back(arr[i]);
}
for(int i=0; i<size; ++i){
B[i].sort(); // sorting! Can Use Insertion Sorting
}
int j=0;
for(int i=0; i<size; ++i){
while(1){
if(B[j].empty()) j++;
else break;
}
arr[i]=B[j].front();
B[j].pop_front();
}
}
int main(void){
float arr[]={.78, .17, .39, .26, .72, .94, .21, .12, .23, .68};
int size=sizeof(arr)/sizeof(float);
BucketSort(arr, size);
for(int i=0; i<size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[size-1]<<endl;
return 0;
}